1. Field of the Invention
The present invention is directed to the field of computer-based database management systems. It is more particularly directed to reducing index size when grid-indexing techniques are applied to multidimensional data stored in a database management system.
2. Description of the Background Art
Indexing techniques are used to quickly access data that has been sorted and assigned an index. Spatial data is typically information associated with geometric shapes such as lines, points, poly-lines, polygons, and surfaces. Spatial data is often very large and may have two, three, or more dimensions. Spatial data may be indexed. Indexing such data by traditional techniques, such as with a B-tree, may not be feasible due to the large amount of computer resources required to index spatial data. Further, B-tree indexing is typically associated with single-dimensional data, not multidimensional data. Therefore, sorting capabilities associated with B-tree indexing are typically not sufficient to be efficiently applied to multidimensional data. To reduce data processing time, various spatial indexing techniques have been studied and developed. Grid indexing is one of these indexing techniques associated with searching spatial multidimensional data, and is used by the product marketed under the trademark IBM DB2® Spatial Extender.
An index enables fast access to a certain subset of data contained in a larger set of data. The index can include a data structure and indicators of the techniques used to build, maintain, and search the data structure for the purpose of accessing a subset of data. For example, an index may define a data structure that is used to access a specific geometric shape included in a set of spatial data. The particular index of the present example may define a data structure that contains references to the minimum-bounding rectangles associated with various geometric shapes in a spatial data set. By accessing locator references associated with the minimum-bounding rectangles the process of accessing particular geometric shapes in a spatial data set is simplified.
A grid index is a space-partitioning. It divides space into rectangles (or squares) called grid cells, using a mathematical formula to determine the boundaries of the grid cells. One approach for such a formula is to define a grid cell size and to lay each boundary as a multiple of the grid cell size. When indexing spatial objects (geometries), the geometries are overlaid with the so defined grid. Depending on the size of the geometry and the grid cell size, a geometry might overlap with more than one grid cell, i.e. it crosses a boundary between grid cells.
When a geometry is indexed in an index maintenance operation, an index key is stored in the index for each grid cell that overlaps with the geometry. Usually, the index entry uniquely identifies the grid cell for which the overlap was noted. For example, the identifier used for the index can be any point in the grid cell, such as its lower-left corner, or its center. Alternatively, other techniques for identifying the overlapping grid cell can be used for the identifier, such as dividing the coordinates by the grid size. For example, using a grid size of 10 with the coordinate value (46, 32) and performing integer arithmetic would identify the grid cell (4, 3) where “4” represents the fourth grid cell in one dimension and “3” represents the third grid cell in another dimension.
Several approaches exist to improve performance of the index maintenance. As previously mentioned, the geometry itself is abstracted by its minimum-bounding rectangle (MBR). That allows for a very simple and fast way to identify the grid cells that overlap with the MBR.
As can be appreciated, a geometry, or its MBR, potentially can overlap many grid cells. Although the computation of the identifiers for all the overlapping grid cells is straightforward if the geometry is abstracted, the task to compute all those identifiers grows linearly with the number of overlaps encountered. Also, storage is needed for all the index entries, which effectively increases costs for storage, and also increases the cost of evaluation of the index because more index entries have to be processed at query time.
A conventional approach to reduce costs is to introduce multiple levels of grids, each level with a different grid size. A geometry is indexed at exactly one grid level. Accordingly, with a larger grid size, fewer index entries are produced. However, the downside of using larger grid sizes is that they do not provide as fine a resolution as smaller grid sizes.
Some implementations of grid indexes (e.g., a grid index implemented in the DB2® Spatial Extender) use a fixed number that sets the maximum number of levels. Although using multiple levels reduces the problem of having many index entries for large geometries, the problem does not entirely vanish. Even at the coarsest grid level, an extremely large geometry can produce thousands of index entries. Also, the grid sizes for the multiple levels are usually tuned to work best for the common set of data and are not tuned for handling such exceptions.
To provide an example, assume two grid levels and the data set to be indexed is the street network of the United States of America. One will probably choose a very small grid size to accommodate the short streets in neighborhoods. The second grid size might be used to accommodate longer streets in cities or between cities. Consider now a road like the I-40 highway, that crosses the entire continent from west to east. Indexing this road on either of the two levels produces a vast number of index entries, whose computation is expensive and which greatly increases the number of indices. This complicates the maintenance of the indices and impacts the data processing capabilities of a database management system underlying the storage of the spatial data.
A conventional approach to handling such large geometries is not to allow such geometries to be indexed at all. If a geometry would produce more index entries than what is defined by a threshold, an error is returned in that conventional approach. In a database context such as the context in which the DB2® Spatial Extender runs, this implies that an insert or update operation would abort due to error.
The conventional approach leaves the user with a number of potentially unattractive options, e.g. to not use an index at all, to not insert the geometry, to break the geometry up into smaller pieces, or to change the index definition to use coarser grid sizes and thus reduce the number of entries produced. A problem with this last option is that changing the index impacts existing data, possibly making performance of the overall index worse.